package com.crab.c05sorting;

import java.util.Arrays;

/**
 * 堆排序 使用最大堆或是最小堆实现，
 * 以从小到大排序为例，数组arr长度是n步骤如下
 * 1、构建最大堆， 堆顶是最大数
 * 2、循环删除堆顶元素，替换到二叉堆的尾部，调整堆产生的新堆
 *
 * @author zfd
 * @version v1.0
 * @date 2022/4/29 16:48
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 7, 5, 1, 2, 9, 6};
        sort(arr);
    }

    public static void sort(int[] arr) {
        // 1 构建最大堆，非叶子节点依次下沉
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        // 循环删除堆顶元素，替换到二叉堆的尾部，调整堆产生的新堆
        for (int i = arr.length - 1; i > 0; i--) {
            // 堆顶交换到堆尾，去除堆尾产生的新堆进行调整
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            downAdjust(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 下沉调整
     *
     * @param arr         待调整的堆
     * @param parentIndex 父节点索引
     * @param length      调整的堆的长度，不一定是原始堆的长度，可以调整部分
     */
    private static void downAdjust(int[] arr, int parentIndex, int length) {
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length) {
            if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            if (temp > arr[childIndex]) {
                break;
            }
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        arr[parentIndex] = temp;
    }
}
